// 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

// 思路：后序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function hasPathSum(root, targetSum) {
    if (!root) {
        return false
    }
    if (!root.left && !root.right) {
        return targetSum - root.val === 0
    }
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
}

// 思路2：遍历
// 时间复杂度：O(n)，n是二叉树的节点数  
// 空间复杂度：O(n)，stack的大小
function hasPathSum(root, targetSum) {
    if (!root) {
        return false
    }
    let stack = [root]
    let valStack = [0]
    while (stack.length) {
        let node = stack.pop()
        let curVal = valStack.pop() + node.val
        if (curVal === targetSum && !node.left && !node.right) {
            return true
        }
        if (node.right) {
            stack.push(node.right)
            valStack.push(curVal)
        }
        if (node.left) {
            stack.push(node.left)
            valStack.push(curVal)
        }
    }
    return false;
}